package _01_动态数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _986_区间列表的交集 {

    public static void main(String[] args) {


        _986_区间列表的交集 v = new _986_区间列表的交集();
        int[][] ins = new int[][]{
                {14, 16},
        };
        int[][] ins1 = new int[][]{
                {7, 13},
                {16, 20},
        };
        int[][] ints = v.intervalIntersection(ins, ins1);

        for (int[] anInt : ints) {
            System.out.println(Arrays.toString(anInt));
        }
    }

    // 思路
    // 准备两个指针，分别指向firstList，secondList的第一个元素
    // 判断第二个指针指向的第一个元素是否小于，第一个指针指向的第二个元素? 将元素加入集合中, first++ , second++,
    // 并且还需要比较secondList的第二个元素，和firstList的第一个元素是否相同
    // 如果不小于的话，那么second++
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> results = new ArrayList<>();
        int first = 0;
        int second = 0;
        while (first < firstList.length && second < secondList.length) {
            // 判断
            int firstFirstEle = firstList[first][0];
            int firstSecondEle = firstList[first][1];
            int secondFirstEle = secondList[second][0];
            int secondSecondEle = secondList[second][1];
            if (firstSecondEle < secondFirstEle) {
                first++;
            } else if (secondSecondEle < firstFirstEle) {
                second++;
            } else {
                //存在交集
                results.add(new int[]{Math.max(firstFirstEle, secondFirstEle), Math.min(firstSecondEle, secondSecondEle)});
                // 判断交集状态
                if (secondSecondEle > firstSecondEle) {
                    first++;
                } else {
                    second++;
                }
            }
        }
        return results.toArray(new int[results.size()][]);
    }

}
